# 给你一个由小写字母组成的字符串 s，和一个整数 k。
#
# 请你按下面的要求分割字符串：
#
# 首先，你可以将 s 中的部分字符修改为其他的小写英文字母。
# 接着，你需要把 s 分割成 k 个非空且不相交的子串，并且每个子串都是回文串。
# 请返回以这种方式分割字符串所需修改的最少字符数。
#

# 方法一：动态规划
# 我们用 f[i][j] 表示对于字符串 S 的前 i 个字符，将它分割成 j 个非空且不相交的回文串，最少需要修改的字符数。在进行状态转移时，我们可以枚举第 j 个回文串的起始位置 i0，那么就有如下的状态转移方程：
#
# f[i][j] = min(f[i0][j - 1] + cost(S, i0 + 1, i))
# 其中 cost(S, l, r) 表示将 S 的第 l 个到第 r 个字符组成的子串变成回文串，最少需要修改的字符数。cost(S, l, r) 可以通过双指针的方法求出：
#
# 初始时将第一个指针置于位置 l，第二个指针置于位置 r；
#
# 每次比较时，判断两个指针指向的字符是否相等。若相等，则这两个位置构成回文，不需要进行修改；若不相等，则为了保证回文，需要修改其中的任意一个字符；
#
# 在每次比较后，将第一个指针向右移动一步，第二个指针向左移动一步，如果第一个指针仍然在第二个指针的右侧，那么继续进行下一次比较。
#
# 上述的状态转移方程中有一些边界情况需要考虑，例如只有当 i >= j 时，f[i][j] 的值才有意义，这是因为 i 个字符最多只能被分割成 i 个非空且不相交的字符串，因此在状态转移时，必须要满足 i >= j 且 i0 >= j - 1。此外，当 j = 1 时，我们并不需要枚举 i0，这是因为将前 i 个字符分割成 j = 1 个非空字符串的方法是唯一的。
#

class Solution:
    def palindromePartition(self, s: str, k: int) -> int:
        def cost(l, r):
            ret, i, j = 0, l, r
            while i < j:
                ret += (0 if s[i] == s[j] else 1)
                i += 1
                j -= 1
            return ret

        n = len(s)
        f = [[10 ** 9] * (k + 1) for _ in range(n + 1)]
        f[0][0] = 0
        for i in range(1, n + 1):
            for j in range(1, min(k, i) + 1):
                if j == 1:
                    f[i][j] = cost(0, i - 1)
                else:
                    for i0 in range(j - 1, i):
                        f[i][j] = min(f[i][j], f[i0][j - 1] + cost(i0, i - 1))

        return f[n][k]
# https://github.com/SakuraGo/leetcodepython3.git
